1. Field of the Invention
The present invention relates to a pattern data generating system for generating pattern data, in which an arbitrary closed graphic pattern whose boundary data is defined on a two-dimensional bit map is filled or painted.
2. Description of the Prior Art
In the field of graphics, it is strongly required to form pattern data by filling or painting an area defined by a polygonal boundary. It is also required to sequentially generate points one by one for an arbitrary curve and to fill or paint a portion surrounded by the curve by using hardware such as DDA (digital differential analyzer).
In a conventional system, in order to satisfy such requirements, filling or painting is performed by using scan conversion for polygons. According to this scan conversion, one direction on a two-dimensional bit map is selected. The selected direction is called a scan direction, and a line parallel thereto is called a scan line. When filling or painting is to be performed, the coordinates of both ends of a line included in a closed graphic pattern are obtained for each scan line, and all the lines in the pattern are painted, thereby filling or painting the overall graphic pattern.
A conventional filling/painting operation of a polygon using scan conversion will now be described, with reference to FIGS. 26 and 27A to 27C. Referring to FIG. 26, reference numeral 71 denotes a rectangular area to be scan-converted; 72 to 77, vertexes of the boundaries of a polygon; 78 to 83, sides of the polygon; and 91, one scan line.
(1) Intersection points P0, P1, P2, and P3 of one scan line 91 and sides of the polygon are obtained. Then, the intersection points are sorted in the order of the coordinate values in the scan direction.
(2) If a given intersection point is an end of a side, i.e., a vertex of the polygon, the given intersection point is processed in accordance with the connection state of the sides of the polygon. In the case shown in FIG. 27A, vertex A is processed as a normal intersection point, while in the case shown in FIG. 27B, one of vertexes B and C is processed as an intersection point. In the case shown in FIG. 27C, vertex D is processed as two intersection points.
(3) The sorted intersection points are paired, and lines having these pairs as their respective ends (lines 84 and 85 in FIG. 26) are filled or painted.
In the conventional system, since processing by software, such as sorting, takes a considerably long period of time, high-speed filling/painting cannot be performed. Further, it is difficult to arrange a hardware system for performing the above processing.
In addition, when lines are to be filled or painted, using a conventional method, vertexes require special processing, as is described in procedure (2). Moreover, if a change in each point of a curve defining an area is generated in a software manner by using a processor, or in a hardware manner by using a DDA or the like, the change in each point need be processed as one line in scan conversion. As a result, a large amount of data must be processed.
As described above, there are various drawbacks to using a conventional system, to fill or paint a closed graphic pattern; for example, high-speed processing cannot be performed, and a hardware system is difficult to arrange.
Meanwhile, the recent availability of high quality low cost printing devices such as laser printers has led to increasing popularity for electronic publishing, and in particular desk top publishing. Electronic publishing typically uses a page description language (PDL) such as PostScript.TM.. Character patterns are defined by outline data to be filled in, which consists of lines and Bezier curves in the case of PostScript, in order that the high quality of generated character patterns is maintained even when characters are enlarged or rotated.
Generally, bit-map filled pattern generation from outline data consisting of lines and curves is hard work for software processing, and takes a long time. So usually, once the font species (Times-Roman etc.) and size are decided, all character patterns of the font set are generated and stored in font cache, and after that patterns in the cache are used for printing or displaying on a CRT display. This approach can work well for languages using an alphabet.
Conversely, for Japanese, Chinese or other languages containing large sets of ideographs, this does not work well because of the huge character set. For these languages, generating all character patterns at the same time and storing all of them in the cache memory is infeasible due to generation time and storage cost. In such a case, we must generate a character pattern every time the character is required (real time generation) or generate a pattern when the character is first used, and then cache recently used characters. In both cases fast pattern generation is necessary.
Generally, Chinese characters are much more complicated in shape than alphanumeric characters, so especially in the case of small size characters a pixel on a contour may be passed by many other contours or even by other parts of the contour itself. In such cases a poor fill algorithm tends to fail in filling and either causes overflow of the filled region or leaves an interior region unfilled.
Further, some kind of adjustment of the patterns may often be required for small size characters, so it is desired that many possible contour rasterizing algorithms can be applied; this is most easily accomplished by making the filling operation independent of the contour rasterizing algorithm. Our requirements for character pattern generation from outline data are summarized as follows:
&lt;1&gt; High speed fill operation:
This leads to a hardware oriented algorithm and makes a hardware implementation possible.
&lt;2&gt; Correctness of fill operation:
For an outline consisting of an arbitrary number of complicated intersecting contours, correctness of the fill operation must be assured.
&lt;3&gt; Clear division of contour rasterization from fill operation:
This makes the fill operation independent of the contour rasterization algorithm so that character transformations may be easily accomplished, and makes hardware implementation easy.
There have been many filling algorithms (ordered edge list algorithms, edge flag algorithms, seed fill algorithms). Most of them treat polygon fill. A representative one is the classical ordered edge list algorithm ("Newman, W. M. Sproull, R. F., Principles of Interactive Computer Graphics, McGraw-Hill, 1979"), which is one of the fastest algorithms suitable for software processing. However it is difficult to implement into hardware because the algorithm needs sorting operations. In this algorithm contour rasterization and filling operation are tightly coupled.
An edge flag algorithm is easier for hardware implementation but it can't be applied to our dx-dy approach because it also treats real edges in the filling operation.
Seed fill is an algorithm in which contour rasterization and filling operations are completely divided. But this algorithm is inferior in efficiency and has difficult problem of seed point determination.